﻿//2909. 元素和最小的山形三元组 II
//给你一个下标从 0 开始的整数数组 nums 。
//如果下标三元组(i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：
//i < j < k
//nums[i] < nums[j] 且 nums[k] < nums[j]
//请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 - 1 。

class Solution {
public:
    int minimumSum(vector<int>& nums)
    {
        //求左边最小的值与右边最小的值
        int n = nums.size();
        vector<int> suf(nums.size());
        suf[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            suf[i] = min(suf[i + 1], nums[i]);
        }
        int ans = INT_MAX, prev = nums[0];
        for (int i = 1; i < n - 1; i++)
        {
            if (nums[i] > prev && nums[i] > suf[i + 1])
            {
                ans = min(ans, prev + nums[i] + suf[i + 1]);
            }
            prev = min(nums[i], prev);
        }
        if (ans == INT_MAX)    ans = -1;
        return ans;
    }
};